package JZOffer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class _连续子数组的最大和_ {
    class Solution {
        public int FindGreatestSumOfSubArray(int[] array) {
            if(array.length == 1) return array[0];
            int[] headSum = new int[array.length];
            int sum = 0;
            for (int i = 0; i < array.length; i++) {
                headSum[i] = sum + array[i];
                sum = headSum[i];
            }
            int res = headSum[0];
            for (int i = 1; i < headSum.length; i++) {
                int now = headSum[i] - findMin(headSum,i);
                if (res < now) res = now;
                if (res < headSum[i]) res = headSum[i];
            }
            return res;
        }

        private int findMin(int[] arr, int pos){
            int min = arr[0];
            for (int i = 0; i < pos; i++) {
                if (arr[i] < min) min = arr[i];
            }
            return min;
        }

    }

    Solution getSolution() {
        return new Solution();
    }

    public static void main(String args[]) {
        _连续子数组的最大和_ c = new _连续子数组的最大和_();
        _连续子数组的最大和_.Solution s = c.getSolution();
        int[] arr = {6,-3,-2,7,-15,1,2,2};
        int res = s.FindGreatestSumOfSubArray(arr);
        System.out.println(res);
        
    }
}
